package com.mrzhou.study.struct.sort;

import com.mrzhou.core.tool.utils.DataUtil;

/**
 * 排序算法之插入排序
 *  排序算法的思想: 下述为个人理解, 视频的描述算法的思路见: classpath: doc/Java数据结构和算法.pdf  ~ 7.72节
 *      将一个待排序的列表分为有序表和无序表, 一般在初次排序时将第一个元素作为有序表, 之后n-1个元素作为无序表
 *      排序时, 从无序表中取出第一个元素, 同有序表中最后一个元素开始比较, 如果比较失败, 则将有序表的元素向右移动,
 *      直到找到无序表中元素可以插入的下标, 无序表的其他元素也以此类推
 */
public class InsertionSort {

    public static void main(String[] args) {
        int arr[] = new int[90000];
        for(int i = 0; i < arr.length; i++) {
            arr[i] = DataUtil.randomInt(0, arr.length);
        }
        Long startTime = System.currentTimeMillis();
        InsertionSort.sort(arr);
        Long endTime = System.currentTimeMillis();
        System.out.println(InsertionSort.toString(arr, 20));
        System.out.printf("插入排序[%d]条数据, 花费的时间: %d\n", arr.length, (endTime - startTime));
    }

    /**
     * 使用while优化后的插入排序:
     *  排序: 90000数据大约: 1000ms
     */
    public static void sort(int arr[]) {
        for(int i = 0; i < arr.length-1; i++) {
            int temp = arr[i+1];
            int j = i;
            while(j >= 0 && temp < arr[j]) { // 这里是先找到temp的插入位置后在插入跳出循环
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j+1] = temp; // 因为while循环中j会先减一, 也就是说j+1才是实际的插入位置
        }
    }

    /**
     * 未优化前的插入排序; 以下代码个人感觉不太像是插入排序, 未看视频代码时写的
     * 排序: 90000数据大约: 7000ms
     */
    public static void sort2(int arr[]) {
        for(int i = 0; i < arr.length-1; i++) {
            int temp = arr[i+1];
            for(int j = i; j >= 0;j--) { // 这段和下面if条件中的代码可以合并到while中, 这样可以在获取到插入位置后在将temp插入到有序表中
                if(temp < arr[j]) {
                    arr[j + 1] = arr[j];
                    arr[j] = temp; // 这段代码, 执行了很多次, 但实际上没有什么意思, 插入排序的核心思想, 应该找到位置之后再将数据插入到有序表中
                }
            }
        }
    }

    public static String toString(int[] arr, int size) {
        StringBuffer sb = new StringBuffer("[");
        for (int i = 0; i < arr.length; i++) {
            if(i%size == 0 && i != 0 && i != arr.length - 1) {
                sb.append("\n");
            }
            if(i == arr.length - 1) {
                sb.append(arr[i]);
            } else {
                sb.append(arr[i]).append(", ");
            }
        }
        return sb.append("]").toString();
    }

}
